Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.


QTRS
  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

A__EQ(s(X), s(Y)) → A__EQ(X, Y)
MARK(take(X1, X2)) → MARK(X2)
MARK(inf(X)) → MARK(X)
MARK(eq(X1, X2)) → A__EQ(X1, X2)
MARK(length(X)) → A__LENGTH(mark(X))
MARK(take(X1, X2)) → MARK(X1)
MARK(inf(X)) → A__INF(mark(X))
MARK(length(X)) → MARK(X)
MARK(take(X1, X2)) → A__TAKE(mark(X1), mark(X2))

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS
  ↳ DependencyPairsProof
QDP
      ↳ EdgeDeletionProof

Q DP problem:
The TRS P consists of the following rules:

A__EQ(s(X), s(Y)) → A__EQ(X, Y)
MARK(take(X1, X2)) → MARK(X2)
MARK(inf(X)) → MARK(X)
MARK(eq(X1, X2)) → A__EQ(X1, X2)
MARK(length(X)) → A__LENGTH(mark(X))
MARK(take(X1, X2)) → MARK(X1)
MARK(inf(X)) → A__INF(mark(X))
MARK(length(X)) → MARK(X)
MARK(take(X1, X2)) → A__TAKE(mark(X1), mark(X2))

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We deleted some edges using various graph approximations

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
QDP
          ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

A__EQ(s(X), s(Y)) → A__EQ(X, Y)
MARK(take(X1, X2)) → MARK(X2)
MARK(eq(X1, X2)) → A__EQ(X1, X2)
MARK(inf(X)) → MARK(X)
MARK(length(X)) → A__LENGTH(mark(X))
MARK(take(X1, X2)) → MARK(X1)
MARK(inf(X)) → A__INF(mark(X))
MARK(length(X)) → MARK(X)
MARK(take(X1, X2)) → A__TAKE(mark(X1), mark(X2))

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 2 SCCs with 4 less nodes.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
QDP
                ↳ QDPOrderProof
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

A__EQ(s(X), s(Y)) → A__EQ(X, Y)

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


A__EQ(s(X), s(Y)) → A__EQ(X, Y)
The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
A__EQ(x1, x2)  =  A__EQ(x1)
s(x1)  =  s(x1)

Recursive path order with status [2].
Precedence:
s1 > AEQ1

Status:
s1: multiset
AEQ1: multiset

The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
                ↳ QDPOrderProof
QDP
                    ↳ PisEmptyProof
              ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
QDP
                ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

MARK(take(X1, X2)) → MARK(X2)
MARK(inf(X)) → MARK(X)
MARK(take(X1, X2)) → MARK(X1)
MARK(length(X)) → MARK(X)

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


MARK(take(X1, X2)) → MARK(X2)
MARK(take(X1, X2)) → MARK(X1)
The remaining pairs can at least be oriented weakly.

MARK(inf(X)) → MARK(X)
MARK(length(X)) → MARK(X)
Used ordering: Combined order from the following AFS and order.
MARK(x1)  =  x1
take(x1, x2)  =  take(x1, x2)
inf(x1)  =  x1
length(x1)  =  x1

Recursive path order with status [2].
Precedence:
trivial

Status:
take2: multiset

The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
                ↳ QDPOrderProof
QDP
                    ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

MARK(inf(X)) → MARK(X)
MARK(length(X)) → MARK(X)

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


MARK(inf(X)) → MARK(X)
The remaining pairs can at least be oriented weakly.

MARK(length(X)) → MARK(X)
Used ordering: Combined order from the following AFS and order.
MARK(x1)  =  MARK(x1)
inf(x1)  =  inf(x1)
length(x1)  =  x1

Recursive path order with status [2].
Precedence:
trivial

Status:
MARK1: multiset
inf1: multiset

The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
                ↳ QDPOrderProof
                  ↳ QDP
                    ↳ QDPOrderProof
QDP
                        ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

MARK(length(X)) → MARK(X)

The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


MARK(length(X)) → MARK(X)
The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
MARK(x1)  =  MARK(x1)
length(x1)  =  length(x1)

Recursive path order with status [2].
Precedence:
length1 > MARK1

Status:
length1: multiset
MARK1: multiset

The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
                ↳ QDPOrderProof
                  ↳ QDP
                    ↳ QDPOrderProof
                      ↳ QDP
                        ↳ QDPOrderProof
QDP
                            ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

a__eq(0, 0) → true
a__eq(s(X), s(Y)) → a__eq(X, Y)
a__eq(X, Y) → false
a__inf(X) → cons(X, inf(s(X)))
a__take(0, X) → nil
a__take(s(X), cons(Y, L)) → cons(Y, take(X, L))
a__length(nil) → 0
a__length(cons(X, L)) → s(length(L))
mark(eq(X1, X2)) → a__eq(X1, X2)
mark(inf(X)) → a__inf(mark(X))
mark(take(X1, X2)) → a__take(mark(X1), mark(X2))
mark(length(X)) → a__length(mark(X))
mark(0) → 0
mark(true) → true
mark(s(X)) → s(X)
mark(false) → false
mark(cons(X1, X2)) → cons(X1, X2)
mark(nil) → nil
a__eq(X1, X2) → eq(X1, X2)
a__inf(X) → inf(X)
a__take(X1, X2) → take(X1, X2)
a__length(X) → length(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.